// Learn TypeScript:
//  - https://docs.cocos.com/creator/manual/en/scripting/typescript.html
// Learn Attribute:
//  - https://docs.cocos.com/creator/manual/en/scripting/reference/attributes.html
// Learn life-cycle callbacks:
//  - https://docs.cocos.com/creator/manual/en/scripting/life-cycle-callbacks.html

import AStarCheckTag from "./AStarCheckTag";
import { AStarNode } from "./AStarNode";

const { ccclass, property } = cc._decorator;

@ccclass
export default class AStar<T extends AStarNode<DATA, TAG>, DATA, TAG> {
  private static Cost90 = 10;//垂直关系的代价
  private static Cost45 = 14;//斜角关系的代价
  //开放列表
  private openSet: Array<T>;
  //关闭列表
  private closeSet: Array<T>;

  private startPoint: T;
  private endPoint: T;

  private allPoint: Array<T>;
  private width: number;
  private height: number;

  //标志量，可走标示，不可走标示，需要提前设定
  private goodTag: AStarCheckTag<TAG>;
  private badTag: AStarCheckTag<TAG>;

  //一些回调
  private searchCB: Function;
  constructor() {
    this.openSet = new Array();
    this.closeSet = new Array();
  }

  setOnSearchCall(cb: Function) {
    this.searchCB = cb;
  }

  findPath(start: T, end: T, all: Array<T>, goodTag: AStarCheckTag<TAG>, badTag: AStarCheckTag<TAG>, w: number, h: number): Array<T> {
    this.startPoint = start;
    this.endPoint = end;
    this.allPoint = all;
    this.goodTag = goodTag;
    this.badTag = badTag;
    this.width = w;
    this.height = h;
    return this.start();
  }

  start(): Array<T> {
    if (this.goodTag.compare(this.badTag) == true) {
      //起点和终点相同，则没有路径
      return null;
    }
    this.startPoint.g = this.gF(this.startPoint, null);//起点的g是0
    this.startPoint.h = this.hF(this.startPoint);
    this.startPoint.f = this.fF(this.startPoint);
    this.openSet.push(this.startPoint);
    this.search();
    //寻路完成
    //检查一下终点是否被赋值了父节点了，如果终点有父节点了，那么代表寻路成功
    if (this.endPoint.hasParent() == true) {
      //生成路径
      let pathPoints = new Array();
      pathPoints.push(this.endPoint);
      this.createPathPoints(pathPoints, this.endPoint);
      return pathPoints;
    }
    return null;
  }

  private createPathPoints(path: Array<T>, point: T) {
    if (point.hasParent() == true) {
      let parent = this.allPoint[point.parentIndex];
      path.push(parent);
      this.createPathPoints(path, parent);
    }
  }

  private search() {
    //从开放列表中找到f值最小的点，取出（弹出）
    let smallFPoint = this.findSmallestFPoint(this.openSet);
    if (smallFPoint == null) {//开放列表中已经没有节点，代表无路可走了,结束
      return;
    }
    //找到他周围的8个点，按条件放入开放列表
    if (this.findPointAroundPoints(smallFPoint) == true) {//如果找到终点了，就结束了
      return;
    }
    //把f最小点放入关闭列表
    this.closeSet.push(smallFPoint);
    this.search();//继续往下找
  }

  private findSmallestFPoint(list: Array<T>): T {
    list.sort((a, b) => a && b && (a.f - b.f));
    return list.shift();
  }

  private findSmallestHPoint(list: Array<T>): T {
    list.sort((a, b) => a && b && (a.h - b.h));
    return list.shift();
  }

  //查找目标点到环绕点
  //返回值 true，找到了终点了
  private findPointAroundPoints(point: T): boolean {
    let findEnd = false;
    for (let x = -1; x <= 1; x++) {
      for (let y = -1; y <= 1; y++) {
        if (x == 0 && y == 0) {
          continue;
        }
        findEnd = this.findPoint(point.corde.y + y, point.corde.x + x, point);
        if (findEnd == true) {
          return true;
        }
      }
    }
    return false;
  }
  //返回值，true找到终点了
  private findPoint(x: number, y: number, parent: T): boolean {
    //首先判断x，y是否超边界？
    if (x < 0 || y < 0 || x > this.height - 1 || y > this.width - 1) {
      return false;
    }
    let index = x * this.width + y;
    let p = this.allPoint[index];
    if (p == null) {
      return false;
    }
    if (this.checkIsEndPoint(p) == true) {
      //把终点的父节点设置为这个父节点
      this.endPoint.parentIndex = parent.myIndex;
      return true;
    }
    if (this.checkPointGood(p) == false || this.checkPointInCloseSet(p) == true) {
      return false;
    }

    //把他放入开放列表中
    p.visitCount++;
    this.putPointInOpenSet(p, parent);
    return false;
  }

  //检查节点是否已经在关闭列表中
  private checkPointInCloseSet(point: T): boolean {
    return this.closeSet.findIndex((a) => a.myIndex == point.myIndex) > -1;
  }
  private checkPointGood(point: T): boolean {
    return point.myTag.compare(this.goodTag);
  }
  private checkIsEndPoint(point: T): boolean {
    return point.myIndex == this.endPoint.myIndex;
  }

  private putPointInOpenSet(point: T, parent: T) {
    let p = this.openSet.find((a) => a.myIndex == point.myIndex);
    if (p) {//如果已经在开放列表中，再次计算他的g值是否比原来的小
      let g = this.gF(p, parent);
      if (g < p.g) {
        p.g = g;
        p.f = this.fF(p);//从新计算f
        p.parentIndex = parent.myIndex;
        if (this.searchCB) {
          this.searchCB(p);
        }
      }
      return;
    }
    p = point//this.allPoint[point.myIndex];
    //计算他的g，h，f值
    //计算该点的ghf
    p.g = this.gF(p, parent);
    p.h = this.hF(p);
    p.f = this.fF(p);
    this.searchCB(p);
    //把它的父节点设置为当前节点
    p.parentIndex = parent.myIndex;
    this.openSet.push(point);
  }

  private gF(point: T, parent: T): number {
    if (parent == null) {
      return 0;
    }
    let dx = Math.abs(point.corde.x - parent.corde.x);
    let dy = Math.abs(point.corde.y - parent.corde.y);
    let cost = 0;
    if (dx * dy == 0) {//垂直关系
      cost = parent.g + AStar.Cost90;
    } else {//斜角关系
      cost = parent.g + AStar.Cost45;
    }
    return cost;
  }
  private hF(point: T): number {
    let dx = Math.abs(point.corde.x - this.endPoint.corde.x);
    let dy = Math.abs(point.corde.y - this.endPoint.corde.y);
    let cost = dx * AStar.Cost90 + dy * AStar.Cost90;
    return cost;
  }
  private fF(point: T): number {
    return point.g + point.h;
  }
}
